package com.xsherl.leetcode.solution;

import java.util.*;

public class GroupAnagrams {

    /**
     *  利用Map存储每个字母异位词的下标，key为字符串所有字符升序排列构成的新字符串
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, Integer> map = new HashMap<>();
        int count = 0;
        List<List<String>> res = new ArrayList<>();
        for (int i = 0; i < strs.length; i++) {
            String s = strs[i];
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            if (map.containsKey(key)){
                int index = map.get(key);
                res.get(index).add(s);
            } else {
                map.put(key, count);
                List<String> list = new ArrayList<>();
                list.add(s);
                res.add(list);
                count++;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
        List<List<String>> lists = new GroupAnagrams().groupAnagrams(strs);
        System.out.println(lists);
    }

}
